package Tree;

import com.sun.source.tree.Tree;

import java.util.Stack;

public class MergeTrees {
    public static void main(String[] args) {

    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2){
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root2);
        stack.push(root1);
        while (!stack.isEmpty()){
            TreeNode node1 = stack.pop();
            TreeNode node2 = stack.pop();
            node1.val += node2.val;
            // 处理右子树，注意我们是以root1为主结构
            if (node2.right != null && node1.right != null) {
                stack.push(node2.right);
                stack.push(node1.right);
            } else {// 以root1为主结构合并树，因此不需要判断root1！=null而root2 == null
                if (node1.right == null) {
                    node1.right = node2.right;
                }
            }
            // 处理左子树
            if (node2.left != null && node1.left != null) {
                stack.push(node2.left);
                stack.push(node1.left);
            } else {
                if (node1.left == null) {
                    node1.left = node2.left;
                }
            }
        }
        return root1;
    }

}
